import java.util.Vector;

public abstract class AStar {	

  public Node initialnode;
  public Node goalnode;     
  public Node n;            
  public Node tempNode;   

  public Vector<Node> OPEN;       
  public Vector<Node> CLOSED;     
  public Vector<Node> M;         

  private long startTime;   
  private long endTime;    

  private int low;          
  private int lowIndex;     

  private int number;       
  
  public void solve() {
    startTime = System.currentTimeMillis();
    initialnode.f = initialnode.h = initialnode.estimate(goalnode);
    initialnode.g = 0;
    OPEN = new Vector<Node>();
    CLOSED = new Vector<Node>();
    M = new Vector<Node>();
    OPEN.add(0, initialnode);
    
    while (true) {
      if (OPEN.size() == 0) {
		  System.out.println("Eroare in rezolvarea problemei!");
		  return;
      }
      
      lowIndex = 0;
      low = OPEN.elementAt(0).f;
      for (int i = 0; i < OPEN.size(); i++) {
		  number = OPEN.elementAt(i).f; 
		  if (number < low) {
			 lowIndex = i;
			 low = number;
		  }
      }
      
      n = OPEN.elementAt(lowIndex);
      OPEN.removeElement(n);
      if (n.equals(goalnode)) {
		  endTime = System.currentTimeMillis();
		  printStatistics(n);
		  return;
      }
      
      M = n.successors();
      for (int i = 0; i < M.size(); i++) {
		  Node s = M.elementAt(i); 
		  s.g = n.g + s.cost;
		  s.h = s.estimate(goalnode);
		  s.f = s.g + s.h;
      }
      
      for (int i = 0; i < M.size(); i++) {
		  tempNode = (Node)M.elementAt(i);
		  tempNode.ancestor = n;
      }
    
      for (int i = 0; i < M.size(); i++) {
		  boolean onCLOSED = isOnVector(M.elementAt(i), CLOSED);
		  if (!(onCLOSED)) 
			 OPEN.add(0, M.elementAt(i)); 
      }
    }
  }
  
  public boolean isOnVector(Node n, Vector v) {
    for (int i = 0; i < v.size(); i++) {
      if (n.equals(v.elementAt(i))) { 
		  return true;
      }
    }
    return false;
  }
  
  public void printStatistics(Node n) {
    System.out.println("Costul solutiei: " + n.f);
    System.out.println("Numarul nodurilor inchise: " + CLOSED.size());
    System.out.println("Numarul nodurilor deschise: " + OPEN.size());
    System.out.println("Timpul (ms): " + (endTime - startTime));
  }    
}